A题初中数学题,不提了
直接上代码吧
代码:https://codeforces.com/contest/1271/submission/66942918
B:
大意:
给你一系列的方块,每一个方块有一个颜色,同时颜色只有黑色和白色之分。定义一个操作:选择两个相邻的方块,使他们俩的方块颜色取反(是对自己而言,不是另一个方块的颜色的取反)。找出一个可行的方案(你不需要找出一个最短的方案,但不能超过3n步)使得所有方块的颜色变为一样,或者知道是无解的。
分析:
这个问题的结果是:使整个序列的颜色一样,也就有两种可能的结果,要么全是白的要么全是黑的。
所以这个问题进一步的可以是:是否存在一种方案使得所有方块全部变成黑色的或者是白色的,我们只要有其中一个做到了就可以直接输出答案,如果两个都不可行就输出无解。
其次注意到n的范围非常小(1 <= n <= 200),200的一个范围甚至可以做3方级的一个算法来求解了,这引导思路到暴力上来思考:假如说现在要让整个序列都变成黑色的,对于序列中每一个是白色的方块,是不是就要在这个位置上翻转一次,我们只考虑选择第i位的方块和第i+1的方块,一直走到倒数第二个方块,看路途中每一个块是不是白色的,如果是的就反转这一位和下一位的方块的颜色;但这个操作最多只能做到倒数第二个方块就必须停止了,这是因为每次操作都必须选择两个方块,对于最后一个方块我们就没有后续的一个方块可供选择了,这个时候如果最后一个还是白色的,说明整个序列无解。同时这样构造出来的方案操作数最多也就n个,绝对不可能触及题目中所说的方案操作数不可超过3n。到此整个题目就可以直接求解了。
这个贪心策略容易想到是一定正确的,并且整个复杂度也不高就O(n)的扫描,对这个题来说还是绰绰有余的;对全部是白色的方案求解也是一样的,这里就不展开了,具体的代码细节可以看代码。
代码:https://codeforces.com/contest/1271/submission/73635278
C:
大意:
现在可以把整个城市的各种信息量化成一个二维的地图,学校在(Sx,Sy)的坐标上。现在要在城市内建一个商店,对每个学生来说,在从家到学校的路径最短的前提下,能走到商店的坐标上就会去商店购物,否则不会。你不能把商店建在学校的位置上,但是与某个学生的坐标重合是可以的。求出一个最佳位置,使得会来购物的学生的数量最多。答案输出最多有几个学生回来购物,以及位置的坐标。
分析:
这道题很显然的要找出一个贪心策略来选择位置,找到这个结论整个题就是白给了。
容易想到:建在学校旁边一定比建在其他地方更好,或者说至少不差。进一步的,在考场上可以猜出一个结论:建在学校旁边,一定是最好的,其次就是在8个位置里选择一个就行了。实际上到这里我们就可以求解这道题了,不过还可以进一步贪心:
我们可以验证这样一个条件:斜角相对学校一定是比上下左右更差的,因为学生要来学校不会是斜着进来,肯定是从上下左右进来的,这样我们就进一步把答案范围缩小到了四个坐标,接着直接枚举答案就可以直接找出答案了。
那么在实际写的时候,我们还要先搞出一个到学校的距离dist,如果到四个点中的某一个坐标的距离比之不大于,就给这个位置的答案+1,最后统计四个中哪一个是最多的就可以了。
代码:https://codeforces.com/contest/1271/submission/67051588
D:
大意:
你现在在玩一个策略游戏。一开始你带着一个有K个人的军队,你的敌人掌握了n座城池。想要攻打第i座城池你需要带领至少Ai个士兵(不是消耗士兵而是需要数量达到)。在你得到了一座城池之后,你会额外获得Bi个士兵;如果你在攻打下了一个城池之后,派出至少一个士兵去镇守,就可以让这座城池的状态变成“占领的”,每个城池都有一个重要度Ci,你的总分就是你占领了的所有的城池的重要度之和。下面有两种方式占领一座城池:
①你当前就在第i个城池,你可以选择留下一个士兵占领他
②游戏中存在着m条下路,每条小路连接着两座城池u,v(u>v),对每个小路来说你可以在城池u派出一个士兵去占领v。
对于你每一步操作来说:你必须是按照顺序攻打城池的(从1到n不能跳跃)。当你攻打下了一个城池之后你就可以得到新的士兵;之后你可以选择派出一个士兵占领这里,或者用小路去占领别的城池。但是你一旦攻打下了下一座城池,之前的所有城池你都不可以再操作了。
在游戏的进程中,一旦你的士兵不够攻打下一座城池或是城池打完了,游戏结束。
答案:如果你无法攻打下所有的城池,输出-1;否则输出你能得到的最大分数。
分析:
这个题的答案输出还是给了一定的简化的,合法的答案必须是攻打下了所有的城池,否则就是-1。
实际上这个题跟另外一个旅游开车的题很像,我们抽象一下过程:
首先你是顺次的从某一个点到下一个点,到达下一个点需要手上持有Ai的军队,到达了之后可以获得Bi的补充,其次你可以选择派出一个人获得分数,或者通过小路占领别的城池获得分数。
在抽象完过程之后我们发现这个题在过程的模拟上还是比较困难的,需要先找到一个贪心的策略简化一下整个答案的求解过程:我们可以这样来做这个问题,利用“反悔”的策略来做。也即,每攻打下一个城池,我们先不要管这个城池是什么情况,直接派出一个人去占领这个城池,然后把这个城池的得分加入一个队列;假如我们后面碰到有一个城池没法攻打了,我们就“反悔”地从前面占领的城池中抽出那个人来,并且去掉那个城池的得分;到这里大概的就可以想到这里可以用优先队列来做,首先每个城池都派出一个人,将城池丢进优先队列里,其次如果要在后面返回就把最不重要的抽出来,从队列中踢掉这个城池并使人数+1。
实际上分析到这里,如果这个题是一个单向的题到此就很明确随便做了,不过这里还要加一个小路的条件,不过也比较好做,这里可以直接类似邻接表的做法,开一个vector连接这个点可以到达的点;当然这里不是从后面往前面连一条有向边,根据我们贪心的过程是从前往后的,实际上这里可以建反边,然后在查答案的过程中就分别查一下小路的边和自己就可以了(我实际的代码中是连接了自己和小路的边)。
代码:https://codeforces.com/contest/1271/submission/67132668
E待写